#include <iostream>
#include <list>
#include <stdlib.h>
#include <string.h> // C string, not C++ string
using namespace std;

#include "construct_greedy_randomized_solution.hh"
#include "utilis.hh"

#define MAX_ATTEMPT 50
#define MAX_LOOP 1000

pair<Graph*, PathMatrix*>* Construct(Graph* G, Graph* G_part, PathMatrix* P_part, int k);
pair<int, int>* mij_greater_than_zero(list<pair<int, int>*> *& lst, int** M, int size);

Path * GetPathCostZeroAccordingG(Graph * G , list<Path*>* Lp) {
	for (list< Path* >::iterator it=Lp->begin(); it != Lp->end(); ++it)
		if(G->CostPath(*it)==0) return (*it);

	return NULL;
};


int GeneralUpdateMatrix(Graph *G_part, PathMatrix *  PM, Path * p, int i, int j) {
	Path * sub_path;

	for (list<int>::iterator it=p->path->begin(); it != p->path->end(); ++it) {
		int node = (*it);
		if(G_part->IsTerminal(node) && node!=i && node!=j) {

			sub_path = p->SubPath(i, node);
			if(GetMatrix(G_part->R, i, node)>0 && PM->IsNodeDisjointTo(sub_path, i, node)) {
				PM->Add(sub_path, i,node);
				DecreaseMatrix(G_part->R, i, node);
				//PrintPath(sub_path);
				//cout << "1: (i, k) " << "("<< i+1 << ", "<< node+1 << ")  ";
				//PrintPath(p, sub_path);
				//cout << "[ConstructGreedyRandomizedSolution][GeneralUpdateMatrix][INFO]: Entre " << "("<< i+1 << ", "<< j+1 << ")" << endl;
			}
			else
				delete sub_path;

			sub_path = p->SubPath(node , j);
			if(GetMatrix(G_part->R, node, j)>0 && PM->IsNodeDisjointTo(sub_path, node, j)) {
				PM->Add(sub_path, node, j);
				DecreaseMatrix(G_part->R, node, j);
				//PrintPath(sub_path);
				//cout << "2: (k, j) " << "("<< node+1 << ", "<< j+1 << ")  ";
				//PrintPath(p, sub_path);
				//cout << "[ConstructGreedyRandomizedSolution][GeneralUpdateMatrix][INFO]: Entre " << "("<< i+1 << ", "<< j+1 << ")" << endl;
			}
			else
				delete sub_path;
		}
	}

	return 0;
};

pair<Graph*, PathMatrix*> * ConstructGreedyRandomizedSolution(Graph * Problem, int k) {
	Graph * G_part = new Graph(Problem->sizeG);
	PathMatrix *  PM;
	pair<Graph*, PathMatrix*> * ret;
	int cant_loop = 0;

	PM = new PathMatrix(Problem->sizeG);

	//Init G_part
	for(int i=0; i<Problem->sizeG; i++) {
		G_part->W[i] = Problem->W[i];
		G_part->_T[i] = Problem->_T[i];
		if (G_part->_T[i]) G_part->actived_node[i] = 1;

		for(int j=i; j<Problem->sizeG; j++) {
			G_part->C[i][j] = Problem->C[i][j];
			G_part->E[i][j] = 0;
			G_part->R[i][j] = Problem->R[i][j];
		}
	}

RETRY:
	ret = Construct(Problem, G_part, PM, k);
	if(!ret) {
		cant_loop++;
		if(cant_loop < MAX_LOOP)
			goto RETRY;
		else
			cout << "[ConstructGreedyRandomizedSolution][INFO]: Not found feasible solution" << endl;
	}

	delete G_part;
	delete PM;

	return ret;
};

pair<Graph*, PathMatrix*> * Construct(Graph* G_problem, Graph* G_part, PathMatrix* P_part, int k) {
	list<pair<int, int>*> * mij_to_process = NULL;
	pair<int, int>* ij = NULL;
	// Es una copia para mantener P para poder reinicializar en caso de que se estanque el algoritmo
	PathMatrix* P_aster;
	list<Path*>* Lp;
	Graph* G_aster, * G_problem_aster;
	Path * p;
	bool ExistAijGreaterThanMaxAttempt = false;

	int** A = new int*[G_problem->sizeG];
	//A es una matriz dinaica, memcpy() pide array de memoria no se permite el doble acceso A[i][j] (no es una matriz)
	for(int i = 0; i < G_problem->sizeG; i++) {
		A[i] = new int[G_problem->sizeG];
		for(int j = i; j < G_problem->sizeG; j++)
			A[i][j] = 0;
	}

	// Copio para poder reestablecer en caso de error
	P_aster = new PathMatrix(P_part);
	G_aster = new Graph(G_part);
	G_problem_aster = new Graph(G_problem);


	//cout << "2222222222" << endl;

	while (!ExistAijGreaterThanMaxAttempt && (ij = mij_greater_than_zero(mij_to_process, G_aster->R, G_problem_aster->sizeG))) {

		//cout << "Edge " << "(" << ij->first << ", " << ij->second << ")" << " M[i][j]: " <<  G_aster->R[ij->first][ij->second] << endl;

		// Esto aca es un buen pire para no sumar orden en restablecimeintos, ademas de resolver otros probelmas
		// que habian (mietras calulo C arreglo lo que rimpi, no sumo orden)
		for(int i = 0; i < G_problem->sizeG; i++) {

			G_problem_aster->actived_node[i] = G_problem->actived_node[i];

			if(G_aster->actived_node[i])
				G_problem_aster->W[i] = 0;
			else
				G_problem_aster->W[i] = G_problem->W[i];

			for(int j = i; j < G_problem->sizeG; j++) {
				G_problem_aster->E[i][j] = G_problem->E[i][j];
				if (G_aster->actived_node[i] && G_aster->actived_node[j] && G_aster->E[i][j])
					G_problem_aster->C[i][j] = 0;
				else
					G_problem_aster->C[i][j] = G_problem->C[i][j];
			}
		}

		G_problem_aster->SubstractWithoutExtremes((*P_aster)[ij->first][ij->second]);

		//cout << "AAAAAAAAA" << endl;
		Lp = G_problem_aster->GetKPathsBetween(ij->first, ij->second, k, G_problem_aster->diameter);
		//cout << "BBBBBBBBB" << endl;

		if(Lp->empty()) {
			A[ij->first][ij->second]++;

			if(A[ij->first][ij->second] < MAX_ATTEMPT) {

				DeleteListPath((*P_aster)[ij->first][ij->second]);
				(*P_aster)[ij->first][ij->second] = ClearCopy((*P_part)[ij->first][ij->second]);

				G_aster->R[ij->first][ij->second] = G_part->R[ij->first][ij->second];

				mij_to_process->push_front(ij);

				//cout << "CCCCCCCC" << endl;
			}
			else {
				ExistAijGreaterThanMaxAttempt = true;
				//cout << "33333333" << endl;
				delete ij;
			}
		}
		else {

			//cout << "DDDDDDDDD" << endl;
			if(!(p = GetPathCostZeroAccordingG(G_aster, Lp))) {
				p = SelectRandom(Lp);
				G_aster->Add(p);
				//cout << "EEEEEEEEEE" << endl;
			}

			P_aster->Add(p, ij->first, ij->second);
			(G_aster->R[ij->first][ij->second])--;
			GeneralUpdateMatrix(G_aster, P_aster, p, ij->first, ij->second);

			if ((G_aster->R[ij->first][ij->second]) > 0) {
				// Lo agrego para sortearlo nuevamente, no esta satisfecho.
				mij_to_process->push_front(ij);
				//cout << "FFFFFFFFFF" << endl;
			}
			else {
				// Ya esta satisfecho.
				delete ij;
				//cout << "GGGGGGGGGGG" << endl;
			}
		}

		DeleteListPath(Lp);
	}


	if (ExistMiiGreaterThanZero(G_aster->R, G_problem->sizeG) || Uncoordinated(G_aster, P_aster)) {
		//cout << "444444444" << endl;
		delete G_aster;
		//cout << "555555555" << endl;
		delete P_aster;
		//cout << "555555555BBBBBBBBBBBBBB" << endl;
		DeleteMatrix(A, G_problem->sizeG);
		//cout << "888888888" << endl;
		delete G_problem_aster;
		//cout << "666666666" << endl;
		DeleteListPairInt(mij_to_process);
		//cout << "4444444444" << endl;
		return NULL;
	}

	//cout << "555555555BBBBBBBBBBBBBB" << endl;
	DeleteMatrix(A, G_problem->sizeG);
	delete G_problem_aster;


	//cout << "555555555555555" << endl;
	return new pair<Graph*, PathMatrix*>(G_aster, P_aster);
};

pair<int, int>* mij_greater_than_zero(list<pair<int, int>*> *& lst, int** M, int size) {
	pair<int, int>* ij;

	//cout << "33333333" << endl;
	if (!lst) {
		//cout << "444444444" << endl;
		lst = new list<pair<int,int>*>();

		for(int i = 0; i < size; i++) // Filas
			for(int j = i; j < size; j++) // Columnas, recordar: son matrices triangulares superiores
				if (M[i][j] > 0) {
					lst->push_front(new pair<int, int>(i, j));
					//cout << "Edge " << "(" << i << ", " << j << ")" << endl;
				}
	}
	//cout << "55555555" << endl;

	while (!lst->empty()) {
		ij = SelectRandom(lst); // retorna un par aleatorio tomado de lst, lo elimina de la lista
		if (M[ij->first][ij->second] > 0) {
			//cout << "6666666666" << endl;
			return ij;
		}
		delete ij;
	}

	//cout << "777777777777" << endl;
	delete lst;
	lst = NULL;
	return NULL;
}
